#include "../src/binomial.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void
permute (unsigned int* x,
         unsigned int  n)
{
  for (unsigned int i = n; i > 1; --i)
    {
      unsigned int j = i * drand48 ();
      unsigned int tmp = x[j];
      x[j] = x[i - 1];
      x[i - 1] = tmp;
    }
}

static int
int_compar (const void* a,
            const void* b)
{
  const unsigned int* xa = a;
  const unsigned int* xb = b;

  return (*xa < *xb) ? 1 : (*xa > *xb) ? -1 : 0;
}

static void
sort (unsigned int* x,
      unsigned int  n)
{
  qsort (x, n, sizeof (*x), int_compar);
}

static int
labels_compar (unsigned int* a,
               unsigned int  na,
               unsigned int* b,
               unsigned int  nb)
{
  if (na < nb) { return -1; }
  else if (na > nb) { return 1; }
  else
    {
      for (unsigned int n = 0; n < na; ++n)
        {
          if (a[n] < b[n]) { return -1; }
          else if (a[n] > b[n]) { return 1; }
        }

      return 0;
    }
}

static char*
to_string (unsigned int* x,
           unsigned int  nx)
{
  char buf[1024];
  off_t off = 0;

  off += sprintf (buf + off, "{ ");

  for (unsigned int n = 0; n < nx; ++n)
    {
      off += sprintf (buf + off, "%u, ", x[n]);
    }

  off += sprintf (buf + off, "}");

  return strdup (buf);
}

static void
test_order_preserving_once (void)
{
  unsigned int k = 5.0 * drand48 ();
  unsigned int l = k + 5.0 * drand48 ();
  unsigned int n_labels_a = k * drand48 ();
  unsigned int n_labels_b = k * drand48 ();

  unsigned int labels_a[n_labels_a];
  unsigned int labels_b[n_labels_b];
  unsigned int all_labels[l];

  for (unsigned int n = 0; n < l; ++n)
    {
      all_labels[n] = n;
    }

  permute (all_labels, l);

  for (unsigned int n = 0; n < n_labels_a; ++n)
    {
      labels_a[n] = all_labels[n];
    }

  sort (labels_a, n_labels_a);
  permute (all_labels, l);

  for (unsigned int n = 0; n < n_labels_b; ++n)
    {
      labels_b[n] = all_labels[n];
    }

  sort (labels_b, n_labels_b);

  unsigned int index_a = set_to_index (labels_a, n_labels_a, l);
  unsigned int index_b = set_to_index (labels_b, n_labels_b, l);
  int cmp_ab = labels_compar (labels_a, n_labels_a, labels_b, n_labels_b);

  assert (( (cmp_ab < 0 && index_a < index_b) ||
            (cmp_ab == 0 && index_a == index_b) ||
            (cmp_ab > 0 && index_a > index_b) ) ||
          ( fprintf (stderr, "cmp_ab = %d, "
                             "set_to_index (%s) = %u, "
                             "set_to_index (%s) = %u\n",
                     cmp_ab,
                     to_string (labels_a, n_labels_a),
                     index_a,
                     to_string (labels_b, n_labels_b),
                     index_b),
            0));
}

static void
test_order_preserving (void)
{
  for (unsigned int n = 0; n < 1000000; ++n)
    {
      test_order_preserving_once ();
    }
}

static void
test_no_duplicates_once (void)
{
  unsigned int k = 5.0 * drand48 ();
  unsigned int l = k + 5.0 * drand48 ();
  unsigned int n_labels = 0;

  for (unsigned int m = 0; m <= k; ++m)
    {
      n_labels += binomial (l, m);
    }

  unsigned int index = n_labels * drand48 ();
  unsigned int labels[l];
  unsigned int depth = index_to_set (index, labels, l);

  assert (depth <= k);

  for (unsigned int m = 1; m < depth; ++m)
    {
      assert (labels[m - 1] != labels[m] || 
              ( fprintf (stderr, "labels = %s\n", to_string (labels, depth)),
                0 ));
    }
}

static void
test_no_duplicates (void)
{
  for (unsigned int n = 0; n < 1000000; ++n)
    {
      test_no_duplicates_once ();
    }
}

static void
test_inverse_once (void)
{
  unsigned int k = 5.0 * drand48 ();
  unsigned int l = k + 5.0 * drand48 ();
  unsigned int n_labels_a = k * drand48 ();

  unsigned int labels_a[n_labels_a];
  unsigned int all_labels[l];

  for (unsigned int n = 0; n < l; ++n)
    {
      all_labels[n] = n;
    }

  permute (all_labels, l);

  for (unsigned int n = 0; n < n_labels_a; ++n)
    {
      labels_a[n] = all_labels[n];
    }

  sort (labels_a, n_labels_a);

  unsigned int index_a = set_to_index (labels_a, n_labels_a, l);
  unsigned int labels_b[l];
  unsigned int n_labels_b = index_to_set (index_a, labels_b, l);
  unsigned int index_b = set_to_index (labels_b, n_labels_b, l);
  int cmp_ab = labels_compar (labels_a, n_labels_a, labels_b, n_labels_b);

  assert (index_a == index_b ||
          ( fprintf (stderr, "index_a = %u, n_labels_a = %u, l = %u, "
                             "cmp_ab = %d, "
                             "set_to_index (%s) = %u, "
                             "set_to_index (%s) = %u\n",
                     index_a,
                     n_labels_a,
                     l,
                     cmp_ab,
                     to_string (labels_a, n_labels_a),
                     index_a,
                     to_string (labels_b, n_labels_b),
                     index_b),
            0));
  assert (cmp_ab == 0);
}

static void
test_inverse (void)
{
  for (unsigned int n = 0; n < 1000000; ++n)
    {
      test_inverse_once ();
    }
}

static void
test_surjective_once (unsigned int l)
{
  unsigned int max_n = 0;

  for (unsigned int k = 0; k < l; ++k)
    {
      max_n += binomial (l, k);
    }

  for (unsigned int n = 0; n < max_n; ++n)
    {
      unsigned int labels_a[l];
      unsigned int n_labels_a = index_to_set (n, labels_a, l);
      unsigned int index_a = set_to_index (labels_a, n_labels_a, l);

      assert (index_a == n);
    }
}

static void
test_surjective (void)
{
  for (unsigned int l = 0; l < 10; ++l)
    {
      test_surjective_once (l);
    }
}

int
main (void)
{
  srand48 (69);

  test_inverse ();
  test_no_duplicates ();
  test_order_preserving ();
  test_surjective ();

  return 0;
}
